The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


The only critical event for this attack occurs at r = 1, where we need the characteristic (a, b) → (0, X) to happen with high probability. Based on the properties of the MDS matrix, we know that there are three single-byte output XORs for s0 that lead to an output XOR of g with Hamming weight of only 8. If the same one of those differences goes into the MDS matrix in both g computations in the second round, then, with probability 2-8, we get an offsetting pair of values in the two g outputs; one g output has some value added to it modulo 232, and the other output has the same value subtracted from it. When the outputs go through the PHT, they lead to only one output word from the whole F being changed, which is what makes this attack possible. Therefore, we choose a = (α, 0, 0, 0) to be a single-byte difference in s0, and b = ROR(a, 8) so that the single-byte difference into the second g computation in round 2 lines up with the single-byte difference in a.

In this attack, we will consider N batches of 256 plaintext pairs, of which at least one is expected to consist of all right pairs. We must choose the inputs to the cipher to allow ourselves to later form such batches. We will then guess some part of the key as needed to check the one known bit of difference going into the fifth round. That key guess will be used to test each batch. Batches that are not made up of right pairs will typically be distinguished after a small number of pairs are checked, because the one-bit difference will be wrong with probability 1/2 in each wrong pair checked with the right key, and in each pair checked with the wrong key. The attack thus consists of the following steps:

1.  Request the encryptions of plaintext blocks necessary to form at least one batch of 256 plaintext pairs that has a very high probability of being made up of only right pairs.
2.  Guess the smallest amount of key material that will let us see the one bit of difference we know in right pairs.
3.  For each such guess, check each batch until one batch turns out to be made of only right pairs.

If there are N batches to be checked, and each takes on average about two trial decryptions’ worth of work, then we end up with 2N work we must do for each guess of key material necessary to see whether the known difference is as we expect it to be.

9.2.3 Building the Batches

Overview. We break the problem into three parts, here. First, we describe how to take a single right pair and generate 255 other right pairs from it. Then, we describe how to take a pair that gets the same 8-bit XOR difference out of both g functions, and use it to generate enough pairs that it is likely that at least one is an actual right pair; i.e., the differences from the two g functions cancel out in the first addition of the PHT. Finally, we describe how to choose pairs so that we are very likely to get at least one pair that gets the same 8-bit XOR difference from both g functions.

Let us suppose we must choose n0 pairs before we get a pair such that both g functions get the same 8-bit XOR difference. (That is, we must choose n0 pairs to get our differential through half of the second round.) We have no way to know which pair has the desired differential, so we must treat all of them as potentially right pairs.

Let us also suppose that given a pair whose differential survives through half of the second round, we must choose n1 related pairs before we find one pair that survives through the whole second round. The rest of the differential occurs with probability one, so one of these pairs is a right pair. We must apply this process to all the potential right pairs to be nearly certain of getting a right pair. Thus, we now have n0n1 pairs to deal with.

Finally, let us suppose that, given a right pair, we must expand it into n2 batches of 256 pairs each before we will be able to detect it. We must do this to all potential right pairs, meaning that we end up with n0n1n2 batches total, each of 256 pairs. Thus, we need to request a total of n0n1n2256 pairs of plaintexts for encryption.

This tells us about the chosen text requirements, but not the workload for the attack. Suppose we have to guess k bits, and that given a guessed partial key, we can check a batch with an average of work equivalent to n3 encryptions. Then the total work factor is 2kn0n1n2n3. As we discuss below, n3 ≈ 1, n2 = 216, n1 = 28, and n0 = 28.

Amplifying Right Pairs. The greatest difficulty in this attack is determining a sequence of inputs that gives us at least one batch of 256 pairs of plaintexts that contains all right pairs. This is necessary because we know only that one bit of difference in the output from the fourth round. Essentially, what we need to do is to "magnify" the effects of a right pair so that a single right pair generates 256 right pairs.

To see how this can be done, let us consider a pair of inputs to the F-function,

X = (C, D) = (c0, c1, c2, c3), (d0, d1, d2, d3)

X* = (C*, D*) = (c0, c1*, c2, c3), (d0, d*1, d2, d3)

such that we know that we have a right pair; i.e., that the two g functions have the same XOR difference after processing X and X*, that these XOR differences have Hamming weights of eight bits only, and that the two XOR differences cancel out during the first addition in the PHT, leading to an output difference of (0, ?). We want to find a way to choose related input pairs that will also be right pairs. To do this, we must consider some details of how right pairs really work. When we compute F(C, D), we find

f0 = g(C) + g(D)

f1 = g(C) + 2g(D)

When we apply an XOR difference to a value, this has the effect of flipping k bits, where k is the Hamming weight of the XOR difference. In terms of mod 232 addition, flipping bit j means adding 2j or subtracting it, depending on whether the bit was on or off. If X, X* is a right pair, it means that g(C), g(D) both got the same 8-bit difference, and that each bit of C covered by a bit of that XOR difference was different than the corresponding bit of D covered by that bit of the difference. In other words, the XOR difference must result in subtracting from g(C) whatever it adds to g(D), so that g(C) + g(D) will be unchanged. This means that simply changing g(C) at random won’t generally produce more right pairs from this one.

There are two ways to make more right pairs from this right pair:

1.  Find a way to change one or more inactive bytes (c0, c2, c3, d0, d2, d3) such that the 8 bits that are changed in g(C), g(D) in the original pair aren’t changed. Since we don’t know which bits those are, this looks hard to do.
2.  Find a way to change those inactive bytes that leads to the same XOR difference being applied to g(C) and g(D). If the same bits are flipped in g(C) and g(D), then the resulting pair will also be a right pair. This is our approach.


Previous Table of Contents Next